// 斐波那契博弈(Fibonacci Game + Zeckendorf定理)
// Zeckendorf定理 ：任何正整数都可以表示成若干个不连续的斐波那契数之和。
// 一共有n枚石子，两位玩家定了如下规则进行游戏：
// 先手后手轮流取石子，先手在第一轮可以取走任意的石子
// 接下来的每一轮当前的玩家最少要取走一个石子，最多取走上一次取的数量的2倍
// 当然，玩家取走的数量必须不大于目前场上剩余的石子数量，双方都以最优策略取石子
// 你也看出来了，根据规律先手一定会获胜，但是先手想知道
// 第一轮自己取走至少几颗石子就可以保证获胜了
// 测试链接 : https://www.luogu.com.cn/problem/P6487
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

const long MAXN = 1000000000000000L;
const int MAXM = 101;
long f[MAXM];
int size;
long n;

inline long read()
{
    char ch = getchar();
    long x = 0, f = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = 10 * x + ch - '0';
        ch = getchar();
    }
    return f * x;
}

void build()
{
    f[0] = 1;
    f[1] = 2;
    size = 1;
    while(f[size] <= MAXN)
    {
        f[size + 1] = f[size] + f[size - 1];
        ++size;
    }
}

long bs(long n)
{
    int l = 0, r = size, m;
    long ans = -1;
    while(l <= r)
    {
        m = (l + r) >> 1;
        if(f[m] <= n)
        {
            ans = f[m];
            l = m + 1;
        }
        else r = m - 1;
    }
    return ans;
}

long compute(long n)
{
    long ans = -1, find;
    while(n != 1 && n != 2)
    {
        find = bs(n);
        if(n == find)
        {
            ans = find;
            break;
        }
        else n -= find;
    }
    // 此处直接 return n 也可以
    // 因为 n 最后一定是符合要求的最小的斐波那契数
    if(ans != -1) return ans;
    else return n;
}

int main()
{
    build();
    n = read();
    printf("%ld\n", compute(n));
    return 0;
}